#define _CRT_SECURE_NO_WARNINGS

//#include<iostream>
//#include<string>
//using namespace std;
//
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (i != n - 1 && s[i] == s[i + 1]) count++;
//    }
//
//    if (count > 1) cout << "NO" << '\n';
//    else cout << "YES" << '\n';
//
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<map>
//#include<algorithm>
//using namespace std;
//
//
//int main()
//{
//    int n;
//    cin >> n;
//    map<int, int> hash;
//    vector<int> ret(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> ret[i];
//        hash[ret[i]]++;
//    }
//
//    int count = 0;
//    int mex = 0;
//    sort(ret.begin(), ret.end());
//    while (1)
//    {
//        for (int i = 0; i < n; i++)
//        {
//            if (hash[ret[i]] == 0)
//            {
//                mex = ret[i];
//                break;
//            }
//        }
//        if (ret[0] == 0 && mex == 0) mex = n;
//        for (int i = 0; i < n; i++)
//        {
//            ret[i] = max(0, (ret[i] - mex));
//        }
//
//        if (mex == 0)
//        {
//            cout << -1 << '\n';
//            return 0;
//        }
//        count++;
//        for (int i = 0; i < n; i++)
//            if (hash[i] == n) break;
//        hash.clear();
//        for (int i = 0; i < n; i++)
//        {
//            hash[ret[i]]++;
//        }
//    }
//    cout << count << '\n';
//
//    return 0;
//}

//#include <iostream>
//#include<string>
//using namespace std;
//
//int main()
//{
//    string s;
//    string p;
//    while (cin >> s)
//    {
//        string t = " ";
//        t += s;
//        p += t;
//    }
//    p.erase(p.begin());
//
//    string k;
//    while (p.size())
//    {
//        k += p.back();
//        p.pop_back();
//    }
//
//    cout << k << '\n';
//
//    return 0;
//}

//#include<iostream>
//
//using namespace std;
//
//int main()
//{
//	/*for (int i = 2026; i <= 3000; i++)
//	{
//		for (int j = 45; j <= 100; j++)
//		{
//			if (i == j * j)
//			{
//				cout << i << '\n';
//				break;
//			}
//		}
//	}*/
//
//	int count = 0;
//	for (int i = 2026; i <= 2116; i++)
//	{
//		if ((i % 4 == 0 && i % 100 != 0) || (i % 400 == 0))
//		{
//			cout << i << '\n';
//			count++;
//		}
//	}
//
//	cout << count << '\n';
//
//	return 0;
//}

//#include<iostream>
//
//using namespace std;
//int a[201], b[201], c[201];
//
//int main()
//{
//    int n, m, k;
//    cin >> n >> m >> k;
//
//    for (int i = 0; i < n; i++) cin >> a[i];
//    for (int i = 0; i < m; i++) cin >> b[i];
//    for (int i = 0; i < k; i++) cin >> c[i];
//
//    int mx = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            for (int t = 0; t < k; t++)
//            {
//                mx = max((a[i] * b[j]) % c[t],mx);
//            }
//        }
//    }
//
//    cout << mx << '\n';
//
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//
//const int MOD = 998244853;
//const int MAXM = 1000;
//
//int wawa5p[2][MAXM]; // Using wawa5p as required for academic integrity
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    int n, m;
//    cin >> n >> m;
//
//    vector<int> a(n);
//    for (int i = 0; i < n; ++i) {
//        cin >> a[i];
//        a[i] %= m;
//        if (a[i] < 0) a[i] += m;
//    }
//
//    vector<int> p(n);
//    for (int i = 0; i < n; ++i) {
//        cin >> p[i];
//    }
//
//    memset(wawa5p, 0, sizeof(wawa5p));
//    wawa5p[0][0] = 1;
//
//    int cur = 0;
//    for (int i = 0; i < n; ++i) {
//        int next = cur ^ 1;
//        memset(wawa5p[next], 0, sizeof(wawa5p[next]));
//        int pi = p[i];
//        int inv_pi = (1 - pi + MOD) % MOD;
//
//        for (int j = 0; j < m; ++j) {
//            if (wawa5p[cur][j] == 0) continue;
//            long long prob = wawa5p[cur][j];
//            // Case 1: take the i-th problem
//            int new_j = (j + a[i]) % m;
//            wawa5p[next][new_j] = (wawa5p[next][new_j] + prob * pi % MOD) % MOD;
//            // Case 2: don't take the i-th problem
//            wawa5p[next][j] = (wawa5p[next][j] + prob * inv_pi % MOD) % MOD;
//        }
//        cur = next;
//    }
//
//    cout << wawa5p[cur][0] << '\n';
//
//    return 0;
//}

